//
// Created by Administrator on 2023-12-23
// https://www.luogu.com.cn/problem/P3912
// 通过
// 线性筛法
//

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 100; //25
//    n=10000; // 1229
    n = 1740948; // out: 130971
//    n = 2115790; //out:156902
//    cin>>n;
    vector<int> primes;
    bool is_p[n+1]={0};
    for (int i = 2; i < n+1 ; ++i)
        is_p[i]=1;
    for (int i = 2; i < n+1; ++i)
    {
        if(is_p[i])
            primes.push_back(i);
        for (int j = 0; j < primes.size() && primes[j]*i<=n; ++j)
        {
            int p =primes[j];
            is_p[primes[j]*i]=0;
            // i%primes[j] and primes[j]%i 都对
            int left =p%i;
            int left2 =i%p;
            // primes[j]%i 结果对 但是会增加计算次数 不符合线性筛法的思路
            // i%primes[j]符合逻辑
            if(i%primes[j]==0)
                break;
        }
    }
    cout<<primes.size();
    return 0;
}